package com.cande.loki.exercise.algorithm.od;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 贪心算法 -- 硬币组合问题
 * 贪心可能找到得不是最优解， 动态规划可以
 */
public class Coin {
//    public static List<Integer> makeChange(int amount, int[] coins) throws Exception {
//        List<Integer> result = new ArrayList<>();
//
//        // 从大到小排序硬币
//        java.util.Arrays.sort(coins);
//
//        for (int i = coins.length - 1; i >= 0; i--) {
//            while (amount >= coins[i]) {
//                amount -= coins[i]; // 减去当前面额
//                result.add(coins[i]); // 记录选择的硬币
//            }
//        }
//        if (amount != 0) {
//            throw new Exception("没有办法找到合适的组合");
//        }
//
//        return result;
//    }
//
//    public static void main(String[] args) throws Exception {
//        int[] coins = {1, 3}; // 硬币面额
//        int amount = 6; // 要找的零钱
//
//        List<Integer> change = makeChange(amount, coins);
//        System.out.println("所需硬币: " + change);
//    }

    //-------------------------------动态规划
    public static int minCoins(int amount, int[] coins) {
        // 初始化 DP 数组，设定为一个较大值
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0; // 0 元需要 0 个硬币

        // 动态规划填充 DP 数组
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i - coin >= 0) { // i - coin 是组合i 除了当前硬币还需要的，剩余金额
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);

                }
            }
        }

        // 返回结果
        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        int[] coins = {1, 3, 4}; // 硬币面额
        int amount = 6; // 要找的零钱

        int result = minCoins(amount, coins);
        if (result != -1) {
            System.out.println("所需最少硬币数量: " + result);
        } else {
            System.out.println("无法找零");
        }
    }
}
